/*
 * @lc app=leetcode.cn id=33 lang=cpp
 *
 * [33] 搜索旋转排序数组
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// @lc code=start
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int length = nums.size();
        int left = 0;
        int right = length - 1;
        int offset = 0;
        int result = -1;
        
        // 二分查找寻找旋转下标
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= nums[0]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        offset = left;      
        
        // 二分查找寻找目标值
        left = 0;
        right = length - 1;
        while (left <= right) {
            int mid_sorted = (left + right) / 2;
            int mid = (mid_sorted + offset) % length;
            if (nums[mid] == target) {
                result = mid;
                break;
            }
            else if (nums[mid] < target) {
                left = mid_sorted + 1;
            } else {
                right = mid_sorted - 1;
            }
        }

        return result;   
    }
};
// @lc code=end

